package top.minuy.algorithm.sort.counting;

import top.minuy.model.Student;

import java.util.Random;

/**
 * 简单计数排序算法
 * 时间复杂度： O(n + R)
 * 首先确定数据范围，本例为 [0,R)
 * 然后新建一个R-0的计数数组，依次遍历整个待排序数组，根据其值对计数数组中对应的元素加一；O(n)
 * 新建一个R-0+1的索引数组，求计数数组的前缀和；O(R)
 * 创建一个原数组的缓存数组，根据索引数组的索引值逐一比对待排序数组的元素，
 * 并放置在缓存数组的对应索引位置，并且当前索引值加一；O(n)
 * 最后返回缓存数组
 *
 * @author Minuy
 * @time 12:49
 * @date 2021/11/12
 */
public class CountingSort {


    public static void main(String[] args) {
        int n = 26 * 26 * 26 * 26;

        Student[] students = new Student[n];
        Random random = new Random();
        int index = 0;
        for (char i = 'a'; i < 'z' + 1; i++) {
            for (char j = 'a'; j < 'z' + 1; j++) {
                for (char k = 'a'; k < 'z' + 1; k++) {
                    for (char l = 'a'; l < 'z' + 1; l++) {
                        students[index] = new Student();
                        students[index].setName("" + i + j + k + l);
                        students[index].setScore(random.nextInt(101));
                        index++;
                    }
                }
            }
        }

        long startTime = System.nanoTime();

        // O(n)
        int R = 101;
        int[] counting = new int[R];
        for (Student student : students) {
            counting[student.getScore()]++;
        }

        // O(R)
        int[] pIndex = new int[R + 1];
        for (int i = 1; i < R + 1; i++) {
            pIndex[i] = pIndex[i - 1] + counting[i - 1];
        }

        // O(n)
        Student[] temp = new Student[n];
        for (Student student : students) {
            temp[pIndex[student.getScore()]++] = student;
        }

        // 时间复杂度 ： O(n + R)

        students = temp;

        long endTime = System.nanoTime();

        for (int i = 0; i + 1 < students.length; i++) {
            if (students[i].getScore() > students[i + 1].getScore()) {
                System.out.println("排序失败！");
                return;
            }

            if (students[i].getScore() == students[i + 1].getScore()) {
                if (students[i].getName().compareTo(students[i + 1].getName()) > 0) {
                    System.out.println(students[i].getName() + " > " + students[i + 1].getName() + " 不稳定排序！");
                    return;
                }
            }
        }

        System.out.println("测试完成： n = " + n + ", time = " + ((endTime - startTime) / 1000000000.0) + "s");

    }


}
